Thực đơn
Đường_đi_Euler Giải thuật tìm chu trình EulerGiả sử G = (V, E) là đồ thị vô hướng, liên thông, tất cả các đỉnh đều có bậc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả các đỉnh đều có bậc lớn hơn 1.
Một cạnh của đồ thị G được gọi là cầu, nếu khi xóa cạnh đó khỏi đồ thị thì làm tăng số thành phần liên thông của G.
1 #include <stdio.h> 2 #include <conio.h> 3 #define TRUE 1 4 #define FALSE 0 5 #define VAIN 99 6 #define MAX 10 7 8 int G[MAX][MAX]; 9 // Ma Tran ke Dinh-Dinh (co Khuyen) 10 int S[MAX][MAX]; 11 // Ma Tran danh dau Cung da su dung 12 int Pred[MAX]; 13 // Mang Nua-Bac-Trong cua 1 Dinh 14 int Succ[MAX]; 15 // Mang Nua-Bac-Ngoai cua 1 Dinh 16 int path[MAX]; 17 // Mang duong di cua chu trinh 18 19 // khai bao ham 20 void ReadData(); 21 void PrintData(); 22 int Check(int k); 23 //bien toan cuc 24 int N, k, l = 0; 25 void Euler(); 26 27 void main() { 28 ReadData(); 29 PrintData(); 30 Euler(); 31 } 32 33 void ReadData() { 34 int i, j; 35 FILE * f = fopen("EU_in.txt", "rt"); 36 37 if (f == NULL) { 38 printf("\nError Loading File!\n"); 39 return; 40 } 41 fscanf(f, "%d", & N); // gia tri dau tien cho biet so dinh cua Do Thi G 42 for (i = 1; i <= N; i++) { 43 Succ[i] = Pred[i] = 0; 44 for (j = 1; j <= N; j++) { 45 S[i][j] = FALSE; 46 // danh dau Cung khong con su dung nua 47 fscanf(f, "%d", & G[i][j]); //lan luot doc cac phan tu MT ke 48 } 49 } 50 fclose(f); 51 for (i = 1; i <= N; i++) 52 for (j = 1; j <= N; j++) 53 if (G[i][j] > 0) { 54 S[i][j] = TRUE; 55 Succ[i]++; 56 Pred[j]++; 57 } 58 // Tinh Bac moi Dinh 59 } 60 61 void PrintData() { 62 clrscr(); 63 int i, j; 64 printf("\nMa Tran Ke G[%d*%d]:\n", N, N); 65 for (i = 1; i <= N; i++) { 66 for (j = 1; j <= N; j++) 67 printf("%4d", G[i][j]); 68 printf("\n"); 69 } 70 } 71 72 void Euler() { 73 FILE * g = fopen("EU_out.txt", "wt"); 74 int i; 75 for (i = 1; i <= N; i++) 76 if ((Pred[i] + Succ[i]) % 2) // neu co dinh bac Le 77 { 78 printf("\nTon tai Dinh %d Bac Le!", i); 79 printf("\nKhong co chu trinh Euler\n"); 80 fclose(g); 81 return; 82 } 83 printf("\nDo thi co chu trinh Euler\n"); 84 int k, ok; 85 // kiem tra va in ra man hinh chu trinh Euler 1 net ve 86 printf("\nKet qua kiem tra xuat phat tu dinh 1:\n"); 87 for (k = 2; k <= N; k++) 88 // kiem tra xuat phat tu Dinh 1 89 { 90 if ((G[1][k] != 0)) 91 // co Cung noi Dinh 1 voi Dinh k 92 { 93 S[1][k] = FALSE; 94 // danh dau Cung(1,k) da duoc su dung 95 ok = Check(k); 96 // xet tiep Dinh k 97 if (ok == FALSE) 98 S[1][k] = TRUE; //duong nay khong nen qua Dinh k=>tra danh dau 99 else // ok==TRUE100 {101 //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua102 printf("Tong so dinh cua chu trinh: %d\n", l + 2);103 fprintf(g, "%d\n", l + 2);104 printf("Cac dinh cua duong di chu trinh:\n");105 printf("1 %d ", k);106 fprintf(g, "1 %d ", k);107 for (int r = l - 1; r >= 0; r--) {108 printf("%d ", path[r]);109 fprintf(g, "%d ", path[r]);110 }111 fclose(g);112 getch();113 return;114 }115 }116 }117 // end for 118 }119 120 int Check(int k) // tiep tuc kiem tra, xuat phat tu Dinh k 121 {122 int i, j, ok;123 for (i = 1; i <= N; i++) {124 if ((S[k][i] == TRUE) && (G[k][i] != 0)) //co Cung tu k den cac Dinh con lai ?125 {126 S[k][i] = FALSE; // neu co, danh dau khong su dung lai Cung(k,i) nua127 ok = Check(i);128 // xet tiep Dinh i den cac Dinh khac129 if (ok == FALSE)130 S[k][i] = TRUE; //lan nay khong nen qua Dinh i => bo danh dau131 else {132 //printf(" %d",i);133 path[l] = i;134 l++;135 return TRUE;136 }137 }138 }139 for (i = 1; i <= N; i++)140 // khi khong con Cung di tu Dinh k nua141 for (j = 1; j <= N; j++) // quet duyet do thi G xem da het Cung chua?142 if (S[i][j] == TRUE)143 // neu con sot Cung tren Ma Tran danh dau S =>144 return FALSE; //huong di theo Dinh k nay la sai=>chon Dinh k khac145 return TRUE;146 // thanh cong, tra ve cac dinh nguoc tren duong di Euler147 }
Thực đơn
Đường_đi_Euler Giải thuật tìm chu trình EulerLiên quan
Đường Đường Trường Sơn Đường cao tốc Bắc – Nam phía Đông Đường Thái Tông Đường (thực phẩm) Đường Huyền Tông Đường hầm tới mùa hạ, lối thoát của biệt ly (phim) Đường lên đỉnh Olympia Đường sắt Việt Nam Đường sắt đô thị Thành phố Hồ Chí MinhTài liệu tham khảo
WikiPedia: Đường_đi_Euler https://commons.wikimedia.org/wiki/Category:Euleri...